use std::cmp::Ordering;

struct SortedArray<T> {
    data: Vec<T>,
    length: usize,
    _alloced: usize,
    equ_func: fn(&T, &T) -> bool,
    cmp_func: fn(&T, &T) -> Ordering,
}

impl<T> SortedArray<T> {
    fn first_index(&self, data: &T, mut left: usize, mut right: usize) -> usize {
        let mut index = left;
        while left < right {
            index = (left + right) / 2;
            match (self.cmp_func)(data, &self.data[index]) {
                Ordering::Greater => left = index + 1,
                _ => right = index,
            }
        }
        index
    }

    fn last_index(&self, data: &T, mut left: usize, mut right: usize) -> usize {
        let mut index = right;
        while left < right {
            index = (left + right) / 2;
            match (self.cmp_func)(data, &self.data[index]) {
                Ordering::Less | Ordering::Equal => left = index + 1,
                Ordering::Greater => right = index,
            }
        }
        index
    }

    fn get(&self, i: usize) -> Option<&T> {
        self.data.get(i)
    }

    fn length(&self) -> usize {
        self.length
    }

    fn new(mut length: usize, equ_func: fn(&T, &T) -> bool, cmp_func: fn(&T, &T) -> Ordering) -> Option<Box<Self>> {
        if length == 0 {
            length = 16;
        }
        let data = Vec::with_capacity(length);
        Some(Box::new(SortedArray {
            data,
            length: 0,
            _alloced: length,
            equ_func,
            cmp_func,
        }))
    }

    fn free(self: Box<Self>) {
        drop(self)
    }

    fn remove(&mut self, index: usize) {
        self.remove_range(index, 1)
    }

    fn remove_range(&mut self, index: usize, length: usize) {
        if index >= self.length || index + length > self.length {
            return;
        }
        self.data.drain(index..index + length);
        self.length -= length;
    }

    fn insert(&mut self, data: T) -> bool {
        let mut left = 0;
        let mut right = self.length;
        let mut index = 0;

        if right > 1 {
            while left != right {
                index = (left + right) / 2;
                match (self.cmp_func)(&data, &self.data[index]) {
                    Ordering::Less => right = index,
                    Ordering::Greater => left = index + 1,
                    Ordering::Equal => break,
                }
            }
        }

        if self.length > 0 && (self.cmp_func)(&data, &self.data[index]) == Ordering::Greater {
            index += 1;
        }

        if self.length + 1 > self._alloced {
            self._alloced *= 2;
            self.data.reserve(self._alloced);
        }

        self.data.insert(index, data);
        self.length += 1;

        true
    }

    fn index_of(&self, data: &T) -> isize {
        let mut left = 0;
        let mut right = self.length;
        let mut index = 0;

        if right > 1 {
            while left != right {
                index = (left + right) / 2;
                match (self.cmp_func)(data, &self.data[index]) {
                    Ordering::Less => right = index,
                    Ordering::Greater => left = index + 1,
                    Ordering::Equal => {
                        left = self.first_index(data, left, index);
                        right = self.last_index(data, index, right);
                        for i in left..=right {
                            if (self.equ_func)(data, &self.data[i]) {
                                return i as isize;
                            }
                        }
                        return -1;
                    }
                }
            }
        }
        -1
    }

    fn clear(&mut self) {
        self.length = 0;
        self.data.clear();
    }
}